# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/18 21:55
@FileName      : 贪心算法部分背包.py
@LastEditors   : None
@Editors       : PyCharm
"""

wares = [10, 20, 30]
prices = [60, 100, 190]
knapsack = 50


def fractional_knapsack(w, p, k):
    for i in range(1, len(w)):
        for j in range(i, 0, -1):
            if p[j] / w[j] > p[j - 1] / w[j - 1]:
                p[j], p[j - 1] = p[j - 1], p[j]
                w[j], w[j - 1] = w[j - 1], w[j]
    weight = k
    result = 0
    i = 0
    while weight > 0:
        W = min(w[i], weight)
        weight -= W
        result += W * (p[i] / w[i])
        if W == w[i]:
            print("总重量为 %d ,总价值为 %d 的商品全部装入" % (w[i], p[i]))
        else:
            print("总重量为 %d ,总价值为 %d 的商品装入 %f%%" % (w[i], p[i], 100 * W / w[i]))
        i += 1
    print("最终收获的商品价值为 %f" % result)
    return result


result = fractional_knapsack(wares, prices, knapsack)
